package top101K.linkedList;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author quan
 * @Description 单链表的排序：给定一个节点数为n的无序单链表，对其按升序排序
 * @Date 2023/7/31 20:44
 */
public class Demo12_SortInList {
    /**
     * 利用数组辅助完成
     * @param head 要排序链表的头结点
     * @return 排序之后的链表的头结点
     */
    public static ListNode sortInList (ListNode head) {
        //新建一个数组
        ArrayList<Integer> arr = new ArrayList<>();
        ListNode pre = head;
        //将链表中的节点存放在数组中
        while (pre != null) {
            arr.add(pre.val);
            pre = pre.next;
        }
        //对数组进行反转
        Collections.sort(arr);
        //将数组变为链表
        ListNode dummyHead = new ListNode(0);
//        dummyHead.next = head;
        ListNode cur = head;
        for (int i = 0; i < arr.size(); i++) {
            int val = arr.get(i);
            ListNode node = new ListNode(val);
            cur.next = node;
            cur = node;
        }
        //因为虚拟头结点之后跟了原始的头结点，在这个头结点之后才是真正的排序后的节点
        //所以这里返回的时候是两个next
//        return dummyHead.next.next;
        return head.next;
    }
}
